package org.example.leetcode.interview.sort;

class LC0324 {
    public void wiggleSort(int[] nums) {
        int[] arr = new int[5001];

        for(int num : nums)arr[num]++;//桶排序
        int n = nums.length;
        int right = 5000;
        //放大数
        for(int i = 1; i < n; i += 2){
            while(arr[right] == 0)right--;
            arr[right]--;
            nums[i] = right;
        }
        //放小数:同样从前往后填充，用的还是从后面的桶拿的数据；这样可以保证避免数据相等
        for(int i = 0; i < n; i += 2){
            while(arr[right] == 0)right--;
            arr[right]--;
            nums[i] = right;
        }
    }
}
